package com.jia.leetCode;

import java.util.*;

/**
 * @program: Leetcode
 * @description: 337.打家劫舍III
 * @author: STU756
 * @create: 2020-08-05 13:14
 */
public class Pro0337 {
    Map<TreeNode, Integer> map = new HashMap<>();
    //上到下
    public int rob2(TreeNode root) {
        if(root == null) {return 0;};
        if(map.containsKey(root)) { return map.get(root);}
        //偷取该节点
        int res1 = 0;
        res1 += root.val;
        if(root.left!=null) {
            res1 += rob(root.left.left) + rob(root.left.right);
        }
        if(root.right != null) {
            res1 += rob(root.right.left) + rob(root.right.right);
        }
        //不偷该节点
        int res2 = 0;
        res2 += rob(root.left) + rob(root.right);
        map.put(root, Math.max(res1, res2));
        return map.get(root);
    }
    //下到上
    public int rob(TreeNode root) {
        if(root == null) { return 0; }
        postorder(root);
        return root.val;
    }


    private void postorder(TreeNode root) {
        if(root.left!=null) {
            postorder(root.left);
        }
        if(root.right!=null) {
            postorder(root.right);
        }
        //选取当前节点
        int res1 = root.val;
        int res2 = 0;//不选取当前节点
        if(root.left!=null) {
            res2 += root.left.val;
            if(root.left.left != null) {
                res1+=root.left.left.val;
            }
            if(root.left.right!=null) {
                res1 += root.left.right.val;
            }
        }
        if(root.right!=null) {
            res2+=root.right.val;
            if(root.right.left!=null) {
                res1 += root.right.left.val;
            }
            if(root.right.right!=null) {
                res1 += root.right.right.val;
            }
        }
        //使用当前节点存储root树下结果的最大值
        root.val = Math.max(res1, res2);
    }
}
